// #define print(...)
#define SIGN(a,b)   ( ((a)^(b)) )
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!dividend||!divisor) return 0;
        if(INT_MIN==dividend && -1==divisor) return INT_MAX;
        int64_t d = dividend, r = divisor, ans = 0, i = 0;
        if(d<0) d=-d; if(r<0) r=-r;
        while(SIGN(d, r)>=0){
            d -= (r<<i);
            ans += (1<<i);
            i++;
        }
        // print("d=", d, ", r=", r, ", ans=", ans, "\n")
        while(d && SIGN(d, r)<0){
            while(i>0 && SIGN(r, d+(r<<i))>=0)
                i--;
        //    print("d(", d, ")+=", r<<i,", ans(", ans, ")-=", 1<<i, "\n")
            d += (r<<i);
            ans -= (1<<i);
        //    print("d=", d, ", ans=", ans, "\n")
        }
        return SIGN(dividend, divisor)<0?-ans:ans;
}
};
